/*
 * @lc app=leetcode.cn id=669 lang=cpp
 *
 * [669] 修剪二叉搜索树
 *
 * https://leetcode-cn.com/problems/trim-a-binary-search-tree/description/
 *
 * algorithms
 * Medium (66.62%)
 * Likes:    522
 * Dislikes: 0
 * Total Accepted:    57.2K
 * Total Submissions: 85.9K
 * Testcase Example:  '[1,0,2]\n1\n2'
 *
 * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树
 * 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
 * 
 * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,0,2], low = 1, high = 2
 * 输出：[1,null,2]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
 * 输出：[3,2,null,1]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数在范围 [1, 10^4] 内
 * 0 <= Node.val <= 10^4
 * 树中每个节点的值都是 唯一 的
 * 题目数据保证输入是一棵有效的二叉搜索树
 * 0 <= low <= high <= 10^4
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {

        //递归遍历
        // if(root == NULL) return NULL;

        // if(root->val < low) {
        //     TreeNode* left = trimBST(root->right, low, high);
        //     return left；
        // }

        // if(root->val > high) {
        //     TreeNode* right = trimBST(root->left, low, high);
        //     return right;
        // }

        // root->left = trimBST(root->left, low, high);
        // root->right = trimBST(root->right, low, high);

        // return root;


        //迭代法
        if(root == NULL) return NULL;

        //先找到一个在区间内的节点 root
        while(root && (root->val < low || root->val > high)) {
            if(root->val < low) root = root->right;
            else root = root->left;
        }

        //此时的cur是一个已经在[low, high]之间的节点
        //修剪左边支树
        TreeNode* cur = root;
        // 此处判断cur的存在是因为，上边下来的root可能不存在，
        // 在不存在的情况下，就没必要进行剪枝的操作
        while(cur != NULL) {
            // 剪枝的时候，cur往右走，
            while(cur->left && cur->left->val < low) {
                cur->left = cur->left->right;
            }
            // 当cur符合条件时，cur一直往左走，试探出靠近low的底线是哪个节点
            // 并且当剪枝操作结束后，cur->left应该是满足条件的，走到头NULL，出循环
            cur = cur->left;
        }

        cur = root;
        while(cur != NULL) {
            while(cur->right && cur->right->val > high) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }

        return root;

    }
};
// @lc code=end

